package com.tree.thrive.business.algorithm.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * @Auther: cheng.tang
 * @Date: 2023/6/8
 * @Description: top-tree
 */
public class BubbleSort {


    public List<Integer> sort(List<Integer> source) {
        List<Integer> dataList = new ArrayList<>(source);
        int size = dataList.size();

        for (int i = 0; i < size - 1; i++) {
            boolean swapped = false;
            /**
             * 2个元素，只需要1轮比较
             * 3个元素，只需要2轮比较
             *  size个元素，只需要size-1轮比较
             */
            for (int j = 0; j < size - 1 - i; j++) {
                /**
                 * 因为j=0,那么只需要有与size-1个元素进行比较
                 * 因为要和后面一个元素比较，因为数组下标不能大于数组长度，所以 j<size-1
                 * 因为经过第i轮排序，顺序仍然有问题有元素个数就减少i个，元素个数在siz-1的基础上要减去已排序的元素个数，即j<size-1-i
                 */
                int nextIndex = j + 1;
                Integer first = dataList.get(j);
                Integer next = dataList.get(nextIndex);
                if (first > next) {
                    dataList.set(nextIndex, first);
                    dataList.set(j, next);
                    swapped = true;
                }
            }
            /**
             * 如果没有发生交换，则说明数组已经有序，可以提前退出循环，从而减少排序的次数。
             * 这样可以避免不必要的比较和交换操作，进一步提高算法的效率。
             */
            if (!swapped) {
                break;
            }
        }
        return dataList;
    }


}
